Recombinação (computação evolutiva)

Em algoritmos genéticos a recombinação ou crossover é um operador genético usado para variar a programação de um cromossomo ou cromossomas de uma geração para a próxima. É análogo à reprodução e recombinação genética, sobre as quais os algoritmos genéticos são baseados. Uma recombinação é um processo de se pegar mais de uma solução progenitora e produzir uma solução descendente a partir deles. Existem métodos para a seleção dos cromossomos. Alguns deles são fornecidos abaixo.

Métodos de seleção de cromossomos para o cruzamento

Amostragem estocástica uniforme (Stochastic universal sampling) O indivíduo é selecionado com base em sua aptidão. A probabilidade de um indivíduo ser selecionado aumenta proporcionalmente à medida de sua aptidão em relação aos demais candidatos a progenitor. Os indivíduos são mapeados em segmentos contíguos de uma reta proporcionais à sua aptidão.
Método da Roleta (Roulette wheel selection) (SCX) Também é conhecido como seleção proporcional à aptidão (Fitness-Proportionate Selection). O indivíduo é selecionado com base em sua aptidão. A probabilidade de um indivíduo ser selecionado aumenta proporcionalmente à medida de sua aptidão em relação aos demais candidatos a progenitor. Difere da amostragem estocástica uniforme simplesmente por ser em uma roleta viciada ao invés de uma reta.^[1]
Seleção Boltzmann (Boltzmann selection) Estabelece uma pressão de seleção variável de acordo com o tempo da pesquisa de solução. Inicialmente, permite a reprodução de indivíduos com baixa aptidão de modo a manter a diversidade da população e evitar convergências prematuras. Com o tempo, vai aumentando a pressão seletiva de modo a favorecer cada vez mais os indivíduos com aptidão mais alta.^[2]
Método do Torneio (Tournament selection) Consite em selecionar uma série de indivíduos da população e estabelecer entre eles uma competição pelo direito de ser um dos progenitores.^[1]
Seleção por ranking (Rank selection)
Seleção Truncada (Truncation selection)
Steady state selection
Seleção local (Local selection)

Técnicas de recombinação

Muitas técnicas de recombinação para organismos existem que usam diferentes estruturas de dados para armazenar elas mesmas.

Recombinação em um ponto

Um único ponto para recombinação é selecionado em ambos os organismos progenitores. Todos os dados além do ponto selecionados são trocados entre os progenitores. Os organismos resultantes são os filhos:

Recombinação em dois pontos

A recombinação em dois pontos necessita que dois pontos sejam selecionados nas cadeias dos organismos progenitores. Tudo que está entre estes dois pontos é trocado entre os progenitores resultando nos filhos:

"Corte e emenda"

Outra variação de recombinação, a abordagem "corte e emenda", resulta na troca de comprimento entre os filhos. A razão para esta diferença é que se escolhe o ponto de corte de cada progenitor separadamente.

Recombinação uniforme e recombinação metade uniforme

Em ambos estes esquemas os progenitores se combinam para formar seus descendentes.

No esquema da recombinação uniforme (UX do inglês Uniform Crossover), os bits do vetor são comparados individualmente entre ambos progenitores. Os bites se intercambiam com uma probabilidade fixada, usualmente 0.5.

No esquema da recombinação metade uniforme (HUX do inglês Half Uniform Crossover), exatamente a metade dos bits que são diferentes são trocados. Por isto se faz necessário se calcular a distância de Hamming (número de bits diferentes). Este número se divide por dois, e o número resultante é a quantidade de bits diferentes que tem que ser intercambiados entre os progenitores.

Recombinação com três progenitores

Nesta técnica, o descendente é derivado a partir de três pais. Eles são escolhidos aleatoriamente. Cada bit do primeiro pai é verificado com o bit do segundo pai se eles são os mesmos. Se são os mesmos então o bit é levado para a prole de outro modo o bit do terceiro pai é levado para a prole. Por exemplo, os seguintes três pais:

pai1 1 1 0 1 0 0 0 1 0

pai2 0 1 1 0 0 1 0 0 1

pai3 1 1 0 1 1 0 1 0 1
produzem a seguinte prole:

prole 1 1 0 1 0 0 0 0 1^[3]

Recombinação para cromossomos ordenados

Dependendo de como o cromossoma representa a solução, uma troca direta não pode ser possível. Um desses casos é quando o cromossomo é uma lista ordenada, como uma lista ordenada das cidades a ser percorrida para o problema do caixeiro viajante. Existem muitos métodos de recombinação para cromossomos ordenados. A já mencionada recombinação de N-pontos pode ser aplicada para cromossomas ordenados também, mas isto sempre necessita de um reparo correspondente, na realidade, alguns métodos de recombinação ordenados derivam desta idéia. Contudo, algumas vezes uma recombinação de cromossomos produz recombinações que violam a restrição de ordenamento e portanto necessitam de ser reparados. Vários exemplos de operadores de recombinação (também operadores de mutação) são dados em ^[4]:

partially matched crossover (PMX): Neste método, dois pontos de recombinação são selecionados aleatoriamente e o PMX atua posicionando trocas sábias. Os dois pontos de recombinação fornecem a seleção correspondente. Ela afeta o cruzamento pelas operações de troca, posição por posição. Neste método os pais são mapeados para o outro, portanto, também se pode chamar partially mapped crossover.^[3]
cycle crossover (CX): Começando em qualquer gene $i$ no progenitor 1, o $i$ -ésimo gene no progenitor 2 torna-se substituído por ele. O mesmo é repetido para o gene deslocado até que o gene que é igual ao primeiro gene inserido fica substituído (ciclo).
order crossover operator (OX1 ou OX): Uma parte de um dos progenitores é mapeada para uma porção do outro progenitor. A partir da porção substituída, o resto é preenchido pelos genes remanescentes, onde genes já presentes são omitidos e a ordem é preservada.
order-based crossover operator (OX2 ou OBX)
position-based crossover operator (POS)
voting recombination crossover operator (VR)
alternating-position crossover operator (AP)
sequential constrictive crossover operator (SCX) ^[5]

Outros métodos possíveis incluem o edge recombination operator.

Recombinações tendenciosas

Para os operadores de cruzamento que trocam seções contíguas dos cromossomos (por exemplo, k-ponto) a ordenação das variáveis pode tornar-se importante. Isto é particularmente verdadeiro quando boas soluções contêm blocos de construção que podem ser perturbados por um operador de crossover que não respeite esta ordem.

Ver também

algoritmo genético

Referências

↑ ^a ^b Linden, Ricardo (2006). Algoritmos Genéticos. Uma Importante Ferramenta da Inteligência Computacional. Rio de Janeiro: Brasport. p. 151-161. ISBN 85-7452-265-1
↑ Ichihara, Jorge de Araújo. «Capítulo III:Algoritmos genéticos». Consultado em 2 de novembro de 2012. Arquivado do original em 25 de julho de 2009
↑ ^a ^b Sivanandam, S.N.; Deepa, S.N. (2008). Introduction to Genetic Algorithms. Berlin, Heidelberg, New York: Springer-Verlag. ISBN 978-3-540-73189-4
↑ Pedro Larrañaga et al., "Learning Bayesian Network Structures by searching for the best ordering with genetic algorithms", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996
↑ Ahmed, Zakir H. "Genetic Algorithm for the Traveling Salesman Problem Using Sequential Constructive Crossover Operator." International Journal of Biometric and Bioinformatics 3.6 (2010). Computer Science Journals. Web. <http://www.cscjournals.org/csc/manuscript/Journals/IJBB/volume3/Issue6/IJBB-41.pdf Arquivado em 23 de março de 2012, no Wayback Machine.>.

Referências adicionais

John Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Michigan. 1975. ISBN 0-262-58111-6.
Larry J. Eshelman, The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination, in Gregory J. E. Rawlins editor, Proceedings of the First Workshop on Foundations of Genetic Algorithms. pages 265-283. Morgan Kaufmann, 1991. ISBN 1-55860-170-8.
Tomasz D. Gwiazda, Genetic Algorithms Reference Vol.1 Crossover for single-objective numerical optimization problems, Tomasz Gwiazda, Lomianki, 2006. ISBN 83-923958-3-2.

Ligações externas

Newsgroup: comp.ai.genetic FAQ - ver seção sobre crossover (também conhecido coo recombinação).

[linden-1] Linden, Ricardo (2006). Algoritmos Genéticos. Uma Importante Ferramenta da Inteligência Computacional. Rio de Janeiro: Brasport. p. 151-161. ISBN 85-7452-265-1

[2] Ichihara, Jorge de Araújo. «Capítulo III:Algoritmos genéticos». Consultado em 2 de novembro de 2012. Arquivado do original em 25 de julho de 2009

[Não_nomeado-yCwE-1-3] Sivanandam, S.N.; Deepa, S.N. (2008). Introduction to Genetic Algorithms. Berlin, Heidelberg, New York: Springer-Verlag. ISBN 978-3-540-73189-4

[4] Pedro Larrañaga et al., "Learning Bayesian Network Structures by searching for the best ordering with genetic algorithms", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996

[5] Ahmed, Zakir H. "Genetic Algorithm for the Traveling Salesman Problem Using Sequential Constructive Crossover Operator." International Journal of Biometric and Bioinformatics 3.6 (2010). Computer Science Journals. Web. <http://www.cscjournals.org/csc/manuscript/Journals/IJBB/volume3/Issue6/IJBB-41.pdf Arquivado em 23 de março de 2012, no Wayback Machine.>.

[1]

[2]

[3]

[4]

[5]